package com.lyq.leetcode.三数之和15;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        int[] nums = new int[]{2, -3, 0, -2, -5, -5, -4, 1, 2, -2, 2, 0, 2, -4, 5, 5, -10};
        System.out.println(main.threeSum(nums));
    }

    /**
     * @param nums 输入数组
     * @return 结果
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> res = new HashSet<>(Set.of());
        Arrays.sort(nums);
        int right;
        int left;
        int middle;
        int temp;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0){
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length; j++) {
                temp = nums[i] + nums[j];
                if (temp>0){
                    break;
                }
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                right = nums.length - 1;
                left = j + 1;

                while (left <= right && nums[left]+temp<=0) {
                    middle = (right + left) / 2;
                    if (nums[middle] + temp == 0) {
                        List<Integer> item = new ArrayList<>();
                        item.add(nums[i]);
                        item.add(nums[j]);
                        item.add(nums[middle]);
                        res.add(item);
                        break;
                    } else if (nums[middle] + temp < 0) {
                        left = middle + 1;
                    } else {
                        right = middle - 1;
                    }
                }
            }
        }
        return res.stream().toList();
    }

    /**
     * @param nums 输入数组
     * @return 结果
     */
//    public List<List<Integer>> threeSum1(int[] nums) {
//        Set<Integer> treeSet = new TreeSet<>();
//        for (int num : nums) {
//            treeSet.add(num);
//        }
//        Set<List<Integer>> res = new java.util.HashSet<>(Set.of());
//
//        int right;
//        int left;
//        int middle;
//        int temp;
//        for (int i = 0; i < nums.length; i++) {
//            if (i > 0 && nums[i] == nums[i - 1]) {
//                continue;
//            }
//            for (int j = i + 1; j < nums.length; j++) {
//                if (j > i + 1 && nums[j] == nums[j - 1]) {
//                    break;
//                }
//                right = nums.length - 1;
//                left = j + 1;
//                temp = nums[i] + nums[j];
//                while (left <= right) {
//                    middle = (right + left) / 2;
//                    if (nums[middle] + temp == 0) {
//                        List<Integer> item = new ArrayList<>();
//                        item.add(nums[i]);
//                        item.add(nums[j]);
//                        item.add(nums[middle]);
//                        res.add(item);
//                        break;
//                    } else if (nums[middle] + temp < 0) {
//                        left = middle + 1;
//                    } else {
//                        right = middle - 1;
//                    }
//                }
//            }
//        }
//        return res.stream().toList();
//    }
}
